α-strongly convex

A Convex function $f$ is $\alpha$-strongly convex if, for all $\mathbf{x},\mathbf{y}$: $$[f(\mathbf{y})-f(\mathbf{x})]-\nabla f(\mathbf{x})^\mathsf{T}(\mathbf{y}-\mathbf{x}) \geq \frac{\alpha}{2}||\mathbf{x}-\mathbf{y}||_2^2$$

Compare to smoothness condition $$[f(\mathbf{y})-f(\mathbf{x})]-\nabla f(\mathbf{x})^\mathsf{T}(\mathbf{y}-\mathbf{x}) \leq \frac{\beta}{2}||\mathbf{x}-\mathbf{y}||_2^2$$

For twice-differentiable scalar function $f$, equivalent to $f''(x) \geq \alpha$ .

When $f$ is convex, we always have that $f''(x) ≥ 0$, so larger values of $α$ correspond to a “stronger” condition.

A function is $\alpha$-strongly convex and β-smooth if for all $\mathbf{x},\mathbf{y}$: $$\frac{\alpha}{2}||\mathbf{y}-\mathbf{x}||_2^2 \leq [f(\mathbf{y})-f(\mathbf{x})]-\nabla f(\mathbf{x})^\mathsf{T}(\mathbf{y}-\mathbf{x}) \leq \frac{\beta}{2}||\mathbf{y}-\mathbf{x}||_2^2$$ (multidimensional generalization)

For scalar functions, a twice-differentiable function $f$ is $\alpha$-strongly convex and β-smooth if for all $x$, $$\alpha \leq f''(x) \leq \beta$$

NOTE: this definition requires scalar function and twice differentiable i.e. $C^2$ relate the two definitions via Taylor's theorem in 1 variable,

Condition number: $\beta/\alpha$